package leetcode.code;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution282_3 implements IDebug {

	private int target;// 目标值
	private List<String> ans;// 答案
	private char[] nums;// num中间加空格
	private int len;// nums数组长度
	private char[] buffer;
	private String[] stack;

	public List<String> addOperators(String num, int target) {
		ans = new ArrayList<>();
		if (num.length() == 1) {
			if (target == Integer.valueOf(num)) {
				ans.add(num);
			}
			return ans;
		}
		this.target = target;// 设置目标
		len = num.length();
		nums = num.toCharArray();
		buffer = new char[len << 1];
		stack = new String[len << 1];
		Stack<String> stack = new Stack<>();// 待计算
		// f(i,j,p)
		// 当前nums第i个位置, 决定i后加什么符号,
		// j是i位置开头数字开头在nums中的位置
		// p缓存在第几位
		f(0, 0, 0, -1);
		return ans;
	}

	private void f(int i, int j, int p, int pstack) {
		System.out.println(i + " " + j + " " + p + " " + pstack);
		buffer[p] = nums[i];// 当前缓存追加字符
		String num = new String(nums, j, i - j + 1);
		if (Long.valueOf(num) > Integer.MAX_VALUE) {// 追加就越界, 无效
			return;
		}
		if (i == len - 1) {// 当i来到最后一位的时候
			String[] temp = new String[len << 1];
			for (int k = 0; k <= p; k++) {
				temp[k] = stack[k];
			}
			this.checkAnswer(temp, num, p, pstack);
			return;
		}
		if (nums[j] != '0') {// 开头不是0 ,后边允许不加符号
			f(i + 1, j, p + 1, pstack);// 决定下一位, 继承开头, p + 1 , 栈没变化
		}
		String backupNum = null;
		if (pstack != -1 && stack[pstack].equals("*")) {
			pstack--;
			backupNum = stack[pstack--];
			long temp = Long.valueOf(backupNum);
			temp *= Long.valueOf(num.toString());
			if (temp > Integer.MAX_VALUE) {
				return;// 数值超过int的是错的
			}
			stack[++pstack] = String.valueOf(temp);
		} else {
			stack[++pstack] = num;
		}
		stack[pstack + 1] = "-";
		buffer[p + 1] = '-'; // i位置后跟着 `-` 操作
		f(i + 1, i + 1, p + 2, pstack + 1);// 决定下一位, 下一位是开头了, 由于多了一个符号 , 下一个位置 = p + 2
		stack[pstack + 1] = "+";
		buffer[p + 1] = '+';
		f(i + 1, i + 1, p + 2, pstack + 1);
		stack[pstack + 1] = "*";
		buffer[p + 1] = '*';
		f(i + 1, i + 1, p + 2, pstack + 1);
		if (backupNum != null) {
			stack[pstack] = backupNum;
			stack[pstack + 1] = "*";
		}
	}

	private void checkAnswer(String[] stack, String num, int len, int pstack) {
		String backupNum = null;
		if (pstack != -1 && stack[pstack].equals("*")) {
			pstack--;
			backupNum = stack[pstack--];
			long temp = Long.valueOf(backupNum);
			temp *= Long.valueOf(num.toString());
			if (temp > Integer.MAX_VALUE) {
				return;// 数值超过int的是错的
			}
			stack[++pstack] = String.valueOf(temp);
		} else {
			stack[++pstack] = num;
		}
		int ans = 0;
		int last = 0;
		while (pstack >= 0) {
			String c = stack[pstack--];
			if (c.equals("+")) {
				ans += last;
			} else if (c.equals("-")) {
				ans -= last;
			} else {
				last = Integer.valueOf(c);
			}
		}
		ans += last;
		if (ans == target) {
			this.ans.add(new String(buffer, 0, len + 1));
		}
	}

	public static void main(String[] args) {
		Solution282_3 so = new Solution282_3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
	}

	@Override
	public void debug1() {
		String num = "123";
		int target = 6;
		String str = "[\"1+2+3\", \"1*2*3\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug2() {
		String num = "232";
		int target = 8;
		String str = "[\"2*3+2\", \"2+3*2\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug3() {
		String num = "00";
		int target = 0;
		String str = "[\"0+0\", \"0-0\", \"0*0\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	@Override
	public void debug4() {
		String num = "105";
		int target = 5;
		String str = "[\"1*0+5\",\"10-5\"]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	public void debug5() {
		String num = "3456237490";
		int target = 9191;
		String str = "[]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

	public void debug6() {
		String num = "9999999999";
		int target = 1409865409;
		String str = "[]";
		List<String> e = HelpDebug.str2liststr(str);
		List<String> r = this.addOperators(num, target);
		HelpDebug.compare(e, r);
	}

}
